/**
 * 实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
 *
 *
 * 示例 1:
 *
 * 输入: 2.00000, 10
 * 输出: 1024.00000
 *
 * 说明:
 *
 * -100.0 < x < 100.0
 * n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
 */
public class Offer_16 {
    public static double myPow(double x, int n) {
        if (x == 0) return 0;
        //n可以用二进制表示
        //9=1001=1*1 + 0*2 + 0*4 + 1*8
        //x^9 = x^(1*1) x^(0*2) x^(0*4) x^(1*8)
        long b = n; //int范围[−2147483648,2147483647]，当n = -2147483648，时执行 n = -n会越界，使用long类型
        double res = 1.0;
        if (n < 0) {
            b = -n;
            x = 1 / x;
        }
        while (b > 0) {
            if ((b & 1) == 1) res *= x;
            x *= x;
            b >>>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(myPow(2, 10));
    }
}
